package com.mid;

/**
 * Created by Lxk on 2019/6/4.
 */
public class Solution148 {
    /**
     * 4->3->1->2->5
     * @param head
     * @return
     */

    private ListNode mergeSort(ListNode head){
        if(head.next==null){
            return head;
        }
        ListNode faster = head,slower = head,pre = null;
        while(faster!=null&&faster.next!=null){
            pre = slower;
            faster = faster.next.next;
            slower = slower.next;
        }
        pre.next = null;
        ListNode l = mergeSort(head);
        ListNode r = mergeSort(slower);
        return mergeRes(l,r);
    }

    private ListNode mergeRes(ListNode part,ListNode part2){
        ListNode dump = new ListNode(0);
        ListNode cur = dump;
        while(part!=null&&part2!=null){
            if(part.val<part2.val){
                cur.next = part;
                cur = cur.next;
                part = part.next;
                cur.next = null;
            }else{
                cur.next = part2;
                cur = cur.next;
                part2 = part2.next;
                cur.next = null;
            }
        }
        if(part!=null){
            cur.next = part;
        }
        if(part2!=null){
            cur.next = part2;
        }
        return dump.next;
    }

    public ListNode sortList(ListNode head) {
        if(head==null){
            return null;
        }
        return mergeSort(head);
    }

    public static void main(String[] args) {
        ListNode node = new ListNode(3);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(1);
        ListNode node4 = new ListNode(2);
        ListNode node5 = new ListNode(5);
        node.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        Solution148 solution148 = new Solution148();
        ListNode head = solution148.sortList(node);
        ListNode cur = head;
        while(cur!=null){
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

}
